COMP90038
Algorithms and Complexity
Lecture 8: Graph Traversal
(with thanks to Harald Søndergaard)
Toby Murray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray
Breadth-First and Depth-First Traversal
Used to systematically explore all nodes of a graph a
•
bc
de
g
h
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
f
Depth-First Traversal
a
bc
de
g
h
3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
f
Depth-First Traversal Nodes visited in this order: a
Start with (any) node
a
bc
de
g
h
4
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
f
Depth-First Traversal Nodes visited in this order: a
Visit the current node’s neighbours depth first (here in alphabetical order)
a
bc
de
g
h
f
5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal Nodes visited in this order:
Visit the current node’s neighbours depth first (here in alphabetical order)
a b
bc
a
g
h
de
f
Remember which nodes we have already visited
6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
to avoid revisiting them
Depth-First Traversal
Nodes visited in this order: a b d
a
bc
g
h
de
7
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
f
Remember which nodes we have already visited
to avoid revisiting them
Depth-First Traversal Nodes visited in this order:
a b d f
bc
de
Back-track when no more new nodes to explore
a
g
h
8
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
f
Depth-First Traversal Nodes visited in this order:
a b d f e
bc
de
Back-track when no more new nodes to explore
a
g
h
9
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
f
Depth-First Traversal Nodes visited in this order:
a b d f e c
bc
de
Back-track when no more new nodes to explore
a
g
h
10
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
f
Depth-First Traversal Nodes visited in this order:
a b d f e c g
bc
de
Back-track when no more new nodes to explore
a
g
h
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
f
Depth-First Traversal
Nodes visited in this order: a b d f e c g h
a
bc
de
g
h
f
12 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Stack Discipline
13
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
When back-tracking, we go back to the most recently- visited node that still has unvisited neighbours
This is simulated by pushing each node onto a stack as it is visited.
Back-tracking then corresponds to popping the stack.
Depth-First Traversal: Stack Discipline
(Simulated) stack:
a
bc
de
g
h
f
14 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal: Stack Discipline
(Simulated) stack:
a
a
bc
de
g
h
f
15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal: Stack Discipline
ab
a
bc
g
h
(Simulated) stack:
b
a
d e
f
Remember which nodes we have already visited
16 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
to avoid revisiting them
Depth-First Traversal: Stack Discipline
(Simulated) stack:
d b a
a
bc
de
g
h
f
17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal: Stack Discipline
(Simulated) stack:
f
d b a
a
bc
de
g
h
f
18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal: Stack Discipline
(back-tracking)
a
bc
de
g
h
(Simulated) stack:
d b a
f
19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal: Stack Discipline
(back-tracking)
a
bc
de
g
h
(Simulated) stack:
b
a
f
20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal: Stack Discipline
(Simulated) stack:
e
b
a
a
bc
d e
g
h
f
21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal: Stack Discipline
(Simulated) stack:
c e
b
a
a
bc
de
g
h
f
22 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal: Stack Discipline
(Simulated) stack:
c e
b
a
a
bc
de
back-tracking … details omitted …
g
h
f
23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal: Stack Discipline
(Simulated) stack:
a
bc
de
g
h
f
24 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal: Stack Discipline
(Simulated) stack:
g
a
bc
de
g
h
f
25 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal: Stack Discipline
(Simulated) stack:
h g
a
bc
de
g
h
f
26 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal: Recursive Implementation
ad
bc e
27 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
28 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
DFS(⟨V,E⟩) Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
29 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
count: 0
DFS(⟨V,E⟩) Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
30 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
DFSEXPLORE(a) count: DFS(⟨V,E⟩)
0
Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
31 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
DFSEXPLORE(a) count: DFS(⟨V,E⟩)
1
Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
32 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
count: 1
DFSEXPLORE(b) DFSEXPLORE(a)
DFS(⟨V,E⟩) Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
33 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
count: 2
DFSEXPLORE(b) DFSEXPLORE(a)
DFS(⟨V,E⟩) Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
34 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
count: 2
DFSEXPLORE(b) DFSEXPLORE(a)
DFS(⟨V,E⟩) Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
35 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
count: 2
DFSEXPLORE(e) DFSEXPLORE(b)
DFSEXPLORE(a) DFS(⟨V,E⟩)
Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
36 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
count: 3
DFSEXPLORE(e) DFSEXPLORE(b)
DFSEXPLORE(a) DFS(⟨V,E⟩)
Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
37 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
count: 3
DFSEXPLORE(e) DFSEXPLORE(b)
DFSEXPLORE(a) DFS(⟨V,E⟩)
Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
38 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
count: 3
DFSEXPLORE(b) DFSEXPLORE(a)
DFS(⟨V,E⟩) Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
39 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
DFSEXPLORE(a) count: DFS(⟨V,E⟩)
3
Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
40 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
count: 3
DFSEXPLORE(c) DFSEXPLORE(a)
DFS(⟨V,E⟩) Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
41 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
count: 4
DFSEXPLORE(c) DFSEXPLORE(a)
DFS(⟨V,E⟩) Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
42 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
count: 4
DFSEXPLORE(c) DFSEXPLORE(a)
DFS(⟨V,E⟩) Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
43 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
DFSEXPLORE(a) count: DFS(⟨V,E⟩)
4
Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
44 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
count: 4
DFS(⟨V,E⟩) Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
45 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
DFSEXPLORE(d) count: DFS(⟨V,E⟩)
4
Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
46 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
DFSEXPLORE(d) count: DFS(⟨V,E⟩)
5
Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
47 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
DFSEXPLORE(d) count: DFS(⟨V,E⟩)
5
Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
48 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
count: 5
DFS(⟨V,E⟩) Call Stack
Depth-First Traversal: Recursive Implementation
ad
bc e
49 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
count: 5
Call Stack
50
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Search:
Recursive Algorithm Notes
Works both for directed and undirected graphs.
The “marking” of nodes is usually done by maintaining a separate
• •
array, mark, indexed by V .
For example, when we wrote “mark v with count”, that would be
•
implemented as “mark[v] := count”.
How to find the nodes adjacent to v depends on the graph
•
representation used.
Using an adjacency matrix adj, we need to consider adj[v,w] Using adjacency lists, for each v , we traverse the list adj[v].
•
for each w in V . Here the complexity of graph traversal is Θ(|V|2).
•
In this case, the complexity of traversal is Θ(|V| + |E|).
Applications of Depth-First Search (DFS)
Easy to adapt DFS to decide if a graph is connected.
How?
bc
e
•
•
ad
51
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Search: Node Orderings
We can order nodes either by the order in which which they are popped from the stack
•
they get pushed onto the stack, or by the order in
Levitin’s compact stack notation
The first subscripts give the order in which nodes are pushed, the second the order in which they are popped off the stack.
52
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Search Forest
DFS can be depicted by the resulting DFS Forest
(DFS Tree for a connected graph)
53 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
a
bc
de
g
h
f
54 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
Nodes visited in this order: a
Start with (any) node
a
bc
de
g
h
f
55 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
Nodes visited in this order: a
Visit all of its neighbours
a
bc
de
g
h
f
56 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
Nodes visited in this order: a b
Visit all of its neighbours
a
bc
de
g
h
f
57 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
Nodes visited in this order: a b c
Visit all of its neighbours
a
bc
de
g
h
f
58 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
Nodes visited in this order: a b c d Then visit all of their
neighbours, and so on a bc
de
f
g
h
59 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
Nodes visited in this order: a b c d e Then visit all of their
neighbours, and so on a bc
de
f
g
h
60 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
Nodes visited in this order: a b c d e f Then visit all of their
neighbours, and so on a bc
de
f
g
h
61 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
Nodes visited in this order: a b c d e f g Then visit all of their
neighbours, and so on a bc
de
f
g
h
62 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
Nodes visited in this order: a b c d e f g h Then visit all of their
neighbours, and so on a bc
de
f
g
h
63 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First vs
Breadth-First Search
Typical Depth-First Search
64 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First vs
Breadth-First Search
Typical Breadth-First Search
65 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
a
bc
de
g
h
f
66 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
a
a
bc
de
g
h
f
67 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
a
bc
de
g
h
f
68 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
b c
a
bc
de
g
h
f
69 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
c
a
bc
de
g
h
f
70 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
c d
a
bc
de
g
h
f
71 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
d
a
bc
de
g
h
f
72 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
d e
a
bc
de
g
h
f
73 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
e
a
bc
de
g
h
f
74 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
ef
a
bc
de
g
h
f
75 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
f
a
bc
de
g
h
f
76 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
a
bc
de
g
h
f
77 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
a
bc
de
g
h
f
78 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
g
a
bc
de
g
h
f
79 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
a
bc
de
g
h
f
80 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
h
a
bc
de
g
h
f
81 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search: Queue Discipline
Traversal Queue:
a
bc
de
g
h
f
82 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search Algorithm
83 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
84
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
BFS Algorithm Notes
BFS has the same complexity as DFS.
•
Again, the same algorithm works for directed
•
graphs as well.
Certain problems are most easily solved by
•
adapting BFS.
•
For example, given a graph and two nodes, a and b in the graph, how would you find the length of the shortest path from a to b?
Breadth-First Search Forest
BFS Tree for this connected graph:
In general, we may get a BFS Forest
85 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
86
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting
We mentioned scheduling problems and their representation by
•
directed graphs.
Assume a directed edge from a to b means that task a must be
•
completed before b can be started.
The graph must be a dag; otherwise the problem cannot be
•
solved.
Assume the tasks are carried out by a single person, unable to Then we should try to linearize the graph, that is, order the nodes
•
multi-task.
•
as a sequence v1,v2,…,vn such that for each edge (vi,vj) ∈ E, we
have vi comes before vj in the sequence (that is, vi is scheduled to happen before vj).
Topological Sorting Example
There are 4 ways to linearise the following graph
Here is one:
87 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
88
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting Algorithm 1
We can solve the top-sort problem with depth-first search:
1. Perform DFS and note the order in which nodes are popped off the stack.
2. List the nodes in the reverse of that order. This works because of the stack discipline.
If (u,v) is an edge then it is possible (given some way of deciding ties) to arrive at a DFS stack with u sitting below v.
•
•
•
Taking the “reverse popping order” ensures that u is listed
•
before v.
Topological Sorting Example Again
Using the DFS method and resolving ties by using alphabetical order, the graph gives rise to the traversal stack shown on the right (the popping order shown in red):
Taking the nodes in reverse popping order yields b, d, a, c, f , e.
89 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
90
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting Algorithm 2
An alternative method would be to repeatedly select a random source in the graph (that is, a node with no incoming edges), list it, and remove it from the graph (including removing its outgoing edges).
This is a very natural approach, but it has the drawback that we repeatedly need to scan the graph for a source.
•
•
However, it exemplifies the general principle of
•
decrease-and-conquer.
Topological Sorting Example Again
Using the source removal method (and resolving ties alphabetically):
Topological sorted order:
91 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting Example Again
Using the source removal method (and resolving ties alphabetically):
Topological sorted order: b
92 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting Example Again
Using the source removal method (and resolving ties alphabetically):
Topological sorted order: b, a
93 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting Example Again
Using the source removal method (and resolving ties alphabetically):
Topological sorted order: b, a, d
94 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting Example Again
Using the source removal method (and resolving ties alphabetically):
Topological sorted order: b, a, d, c
95 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting Example Again
Using the source removal method (and resolving ties alphabetically):
Topological sorted order: b, a, d, c, e
96 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting Example Again
Using the source removal method (and resolving ties alphabetically):
Topological sorted order: b, a, d, c, e, f
97 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
98
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Next time
•
So next we turn our attention to the very useful “decrease and conquer” principle
(Levitin Chapter 4).